package Leetcode第二期;

/**
 * @author : K k
 * @date : 9:06 2020/10/20
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1:
 *
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 *
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 */
public class 重排链表_143 {

    //思路：快慢指针平分 一头一尾取元素
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        //找中点，链表分成两个
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //第二个链表的头结点 要进行反转
        ListNode newHead = slow.next;
        slow.next = null;
        reverseList(newHead);
        //交替构造
        //链表节点依次连接
        while (newHead != null) {
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }

    //反转链表
    private ListNode reverseList(ListNode head) {
        if (head == null || head.next==null) {return head;}
        ListNode ret=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return ret;//返回最后一个节点
    }
}
